1. Field
This application relates to communication networks and, more particularly, to a method and apparatus for determining protection transmission unit allocation.
2. Description of the Related Art
Data communication networks may include various computers, servers, hubs, switches, nodes, routers, proxies, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
The various network elements on the communication network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network elements, various aspects of what the protocol data units should look like, and how protocol data units should be handled or routed through the network by the network elements.
Communication networks may be configured in multiple different topologies, such as ring-based topologies and mesh topologies. Ring-based topologies advantageously provide fast protection switching such that if a failure is experienced on a portion of the ring, traffic may be diverted the other way through the ring to minimize disruption on the network. One common ring-based topology which has been successfully deployed in North America and several other parts of the World is commonly referred to as Synchronous Optical NETwork (SONET) Bi-Directional Switched Ring (BLSR). Another similar standard that is used extensively in Europe and several other areas is commonly referred to as Synchronous Data Hierarchy (SDH) Multiplex Section Shared Protection Ring (MS-SPRing). Although one or more embodiments of the invention may be described herein in connection with a SONET network implementation, the invention is not limited in this manner and may be more broadly utilized in connection with any other type of ring-based or mesh-based networks.
Mesh topologies enable nodes on the mesh to communicate with multiple other nodes so that traffic is not required to be communicated to a specific node as it progresses through the network. To increase the speed at which traffic may be protection switched through a mesh network without requiring a new path to be found through the mesh network, it is possible to create virtual rings and reserve a portion of the bandwidth on those rings to carry protection traffic in the event of a failure. Logical restoration paths in a mesh-network are commonly referred to as p-cycles. P-cycle enable the network devices to perform fast link restoration protection without requiring notification of the source or destination nodes. Thus, in a mesh network the working path will be carried over the mesh network, while the restoration path will be carried over the logical ring. Restoration of traffic from a failed arc, however, should not have an unplanned negative impact on traffic which normally uses the restoration path. Mesh networks may be based on the SONET physical layer or other physical layer protocol. Rings, p-cycles, and other loop-related protection arrangements will be referred to herein as protection cycles.
SONET/SDH divides the total capacity on a link up into time slots, referred to in the standards as Synchronous Telecommunication Signals (STS#s). Conventionally, traffic to be transported through a SONET/SDH network was placed on a particular STS# or group of contiguous STS#s when it entered the ring and was transported through the ring on the same time slot(s) on every span between every pair of network elements forming the SONET ring. Maintaining traffic on the same time slot on all spans in the ring provided an easy way to locate the traffic on the protection path in the even of a failure, but proved to be inefficient in that bandwidth may be stranded on particular spans and unable to be allocated to a particular flow if that same time slot weren't available all the way through the ring. Similarly, the requirement that STS#s be placed on contiguous time slots resulted in time slots not being allocated to a channel despite the fact that there was sufficient bandwidth, in the aggregate, to handle the channel on the ring. For example, if a channel needed 3 STS#s and there were two sets of 2 contiguous STS#s, the flow would not be able to be passed onto the ring despite the fact that there was sufficient capacity on the ring to handle the new channel.
To overcome these limitations, a proposal has been made to allow a given connection to be carried on different time slots on different spans on the SONET ring. This has been conventionally referred to as Time Slot Interchange, which is described for example in U.S. patent Ser. No. 10/144,842, entitled Method And Apparatus For Bandwidth Optimization In Network Ring Topology, filed May 15, 2002, the content of which is hereby incorporated herein by reference.
SONET/SDH-based ring topology networks and other ring-topology networks generally contain a working path and a protection path for each span on the ring. The ring, either physical or logical as in the case of a mesh network, allows traffic to be communicated between two nodes on the ring in either direction so that if there is a span or node failure on the ring the traffic may be routed around the failure by reversing the direction of the traffic on the ring. SONET/SDH optical network rings are typically either a two fiber ring or a four fiber ring. A two fiber ring uses two fibers between each span of the ring. Each fiber span carries both the working-traffic channel and the protection channel whereby on each fiber, only a maximum of half the channels are defined as working channels and the other half of the channels defined as protection channels. A four fiber ring uses four fibers for each span of the ring. Working and protection pairs are carried over different fibers. That is, two fibers, each transmitting in opposite directions, carry the working channels; two other fibers carry the protection channels. Conventionally, when traffic was protection switched from the working path to the protection path, the time slot allocation was maintained so that the network elements in the ring would know which transmission unit, e.g. which time slot, on the protection path the connection could be located.
When the assumption that traffic will use the same time slot throughout the ring is removed, it becomes necessary to communicate the protection transmission unit allocation to the nodes on the ring. For example, assume that a given node was handling a connection that was received on the working path on STS#1 and was transmitted on STS#2 on the working path. If the node fails, it is unclear whether this traffic should be carried on STS#1, STS#2, or on a completely different STS# on the protection path.
This becomes more complicated in mesh-topology networks in which multiple paths may be used to back up flows through a given node. For example, if two nodes A and B are connected by three links, it is possible to set the maximum bandwidth on each link to be 66% and reserve 33% on each link as back-up. In the event that one of the links fails, the 66% traffic from the failed link may be split and passed over the 33% backup capacity on each of the other two links to achieve total restoration over the links.
One attempt to address this problem was to use a centralized approach whereby a centralized controller would generate tables and disseminate these tables to the nodes on the ring so that, upon occurrence of a failure, the nodes would know where the traffic would be located. This approach is described in more detail in U.S. patent application Ser. No. 10/144,842, the content of which is hereby incorporated by reference. Unfortunately, every time a new connection was added or a connection was deleted, these maps needed to be changed. Additionally, the deployed base of SONET/SDH networks did not have a convenient centralized computing platform, which complicated deployment into existing networks. Finally, when multiple failure scenarios were to be taken into account, the number of maps required to be generated and maintained grew to be quite large. Accordingly, it would be advantageous to have another method for determining protection transmission unit allocation.